package array;

/**
 * @author Liaorun
 */
public class KthMissingPositiveNumber {

    public static void main(String[] args) {
        System.out.println(findKthPositive(new int[]{1, 2, 3}, 4));
    }


    public static int findKthPositive(int[] arr, int k) {
        int l = 0;
        int r = arr.length - 1;
        // 0 ~ n -1
        int m;
        // 右边界的位置 = 数组的长度，这样如果查找数组中所有的数都不存在 (存在的缺失的整数个数 >=  k)的情况
        // 在31行代码处 find - 1 仍然能获取到正确的值
        int find = arr.length;
        while (l <= r) {
            m = (l + r) / 2;
            if (arr[m] - (m + 1) >= k) {
                // 当前中点的值 - 当前中点下标 + 1 == 存在的缺失的整数个数 >=  k (需要找的第k个缺失的整数)
                // 记录当前中点下标
                find = m;
                // 为了确定当前的范围是不是最小的范围
                // 在左侧继续二分查找，右指针 = 中点下标 -1
                r = m - 1;
            } else {
                // 当前中点的值 - 当前中点下标 + 1 == 存在的缺失的整数个数 <  k (需要找的第k个缺失的整数)
                // 在右侧继续二分查找，右指针 = 中点下标 -1
                l = m + 1;
            }
        }


        // 找到最小范围的右边界前一个值 =  如果右边界的下标 == 0 ? 0 : 找到最小范围的右边界前一个值
        int preValue = find == 0 ? 0 : arr[find - 1];

        // 到右边界-1的位置已经存在多少个缺失的整数 = 右边界-1位置的值 - 右边界的下标值
        int under = preValue - find;

        // 第k个缺失的整数 = 找到最小范围的右边界前一个值 + (k - 到右边界-1的位置已经存在多少个缺失的整数)
        return preValue + (k - under);
    }
}
